#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <functional>
using namespace std;

// 邻接矩阵存储图
namespace matrix
{
	// V：顶点的类型
	// W：权值的类型
	// Direction：表示有向图还是无向图
	template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Graph<V, W, MAX_W, Direction> Self;

	public:
		// 强制生成默认的构造函数
		Graph() = default;

		// vertexs：顶点信息的起始地址
		// n：顶点的个数

		Graph(const V *vertexs, int n)
			: _n(n),
			  _vertexs(n),
			  _matrix(n, vector<W>(n, MAX_W))
		{
			for (int i = 0; i < n; i++)
			{
				_vertexs[i] = vertexs[i];
				_index[vertexs[i]] = i;
			}
		}

		// 构建邻接表
		// 1. 通过IO输入
		// 2. 读取文件
		// 3. 添加边 --> 为了方便测试，我们使用添加边

		size_t GetVertexIndex(const V &vertex)
		{
			// 如果没找到返回-1
			if (_index.count(vertex) == 0)
			{
				cout << "无效定点：" << vertex << endl;
				throw invalid_argument("无效顶点");
			}
			return _index[vertex];
		}

		void _AddEdge(size_t srci, size_t desti, const W &w)
		{
			// 在获取顶点中判定了是否为有效顶点，此处则不用判断是否合法
			_matrix[srci][desti] = w;
			// 如果是无向图，则还要添加
			if (Direction == false)
				_matrix[desti][srci] = w;
		}
		// 添加(srcv,destv) srcv -> destv
		// w：权值
		void AddEdge(const V &srcv, const V &destv, const W &w)
		{
			size_t srci = GetVertexIndex(srcv);
			size_t desti = GetVertexIndex(destv);
			_AddEdge(srci, desti, w);
		}

		// 打印邻接矩阵
		void Print()
		{
			// 1.打印下标与顶点的映射
			for (int i = 0; i < _n; i++)
			{
				cout << "[" << i << "] -> " << _vertexs[i] << endl;
			}
			cout << endl;
			// 2.打印整个邻接表
			printf("  ");
			for (int i = 0; i < _n; i++)
			{
				printf("%4d", i);
			}
			cout << endl;
			for (int i = 0; i < _n; i++)
			{
				printf("%d ", i);
				for (int j = 0; j < _n; j++)
				{
					if (_matrix[i][j] == MAX_W)
						printf("%4c", '*');
					else
						printf("%4d", _matrix[i][j]);
				}
				cout << endl;
			}
			cout << endl;
		}

		void _bfs(int srci, vector<bool> &_vis, queue<int> &que)
		{
			while (!que.empty())
			{
				int level = que.size();
				while (level)
				{
					int src = que.front();
					que.pop();
					cout << _vertexs[src] << " ";
					// 获取与该顶点相邻的顶点
					// 无向图中邻接表是对称的，因此只要遍历左下角角or右上角
					for (int j = 0; j < _n; j++)
					{
						if (_matrix[src][j] != MAX_W && _vis[j] == false)
						{
							que.push(j);
							_vis[j] = true;
						}
					}
					level--;
				}
				cout << endl;
			}
		}

		void BFS(const V &src)
		{
			size_t srci = GetVertexIndex(src);
			vector<bool> _vis(_n);
			queue<int> que;
			que.push(srci);
			_vis[srci] = true;
			_bfs(srci, _vis, que);
			// 将不是与srci连通的顶点也一起访问
			for (int i = 0; i < _n; i++)
			{
				if (_vis[i] == false)
				{
					que.push(i);
					_vis[i] = true;
					_bfs(i, _vis, que);
				}
			}
			cout << endl;
		}

		void _dfs(int srci, vector<bool> &vis)
		{
			vis[srci] = true;
			cout << _vertexs[srci] << " ";
			for (int i = 0; i < _n; i++)
			{
				if (_matrix[srci][i] != MAX_W && vis[i] == false)
				{
					_dfs(i, vis);
				}
			}
		}

		void DFS(const V &src)
		{
			size_t srci = GetVertexIndex(src);
			vector<bool> vis(_n);
			_dfs(srci, vis);
			cout << endl;
			for (int i = 0; i < _n; i++)
			{
				if (vis[i] == false)
				{
					_dfs(i, vis);
					cout << endl;
				}
			}
		}

		struct Edge
		{
			int _srci;
			int _desti;
			W _w;
			Edge(int src = -1, int des = -1, W w = W())
				: _srci(src),
				  _desti(des),
				  _w(w)
			{
			}

			bool operator>(const Edge &e) const
			{
				return _w > e._w;
			}
		};

		// 最小生成树
		W Kruskal(Self &minTree)
		{
			// 0.对minTree初始化
			minTree._matrix.resize(_n, vector<W>(_n, MAX_W));
			minTree._vertexs = _vertexs;
			minTree._n = _n;
			// 1.获取所有边，并构建小根堆，大于符号，直接重载> 使用greater
			priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
			for (int i = 0; i < _n; i++)
			{
				// 最小生成树是无向图 --> 使用右上角
				for (int j = i + 1; j < _n; j++)
				{
					if (_matrix[i][j] != MAX_W)
					{
						pq.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}
			// 2.定义集合 - 最小生成树集合，desti不在该顶点集合中才可以选择
			vector<int> ufs(_n, -1); // 并查集
			// 找根
			auto FindRoot = [&ufs](int x)
			{
				while (ufs[x] >= 0)
					x = ufs[x];
				return x;
			};
			// 合并集合
			// 需要捕获lambda FindRoot，否则UnionSet内不能使用
			auto UnionSet = [&ufs, &FindRoot](int x, int y)
			{
				int r1 = FindRoot(x);
				int r2 = FindRoot(y);
				if (r1 != r2)
				{
					ufs[r1] += ufs[r2];
					ufs[r2] = r1;
				}
			};
			// 是否在同一个集合
			auto InSet = [&ufs, &FindRoot](int x, int y)
			{
				int r1 = FindRoot(x);
				int r2 = FindRoot(y);

				if (r1 == r2)
					return true;
				else
					return false;
			};

			// 构建最小生成树
			int n = 0;
			W w = W();
			while (!pq.empty())
			{
				auto eg = pq.top();
				pq.pop();
				if (InSet(eg._srci, eg._desti) == false)
				{
					cout << _vertexs[eg._srci] << " " << _vertexs[eg._desti] << " - " << eg._w << endl;
					w += eg._w;
					// src,dest 不在同一个集合，则选择该边构建最小生成树
					minTree._AddEdge(eg._srci, eg._desti, eg._w);

					// 合并到一个集合
					UnionSet(eg._srci, eg._desti);
					n++;
				}

				if (n == _n - 1)
					return w;
			}

			return W();
		}

		W Prim(Self &minTree, const V &src)
		{
			// 0.对minTree初始化
			minTree._matrix.resize(_n, vector<W>(_n, MAX_W));
			minTree._vertexs = _vertexs;
			minTree._n = _n;
			// 1.将与起点连通的边放入小根堆
			priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
			vector<bool> vis(_n); // 已使用集合
			W w = W();
			int srci = GetVertexIndex(src);
			vis[srci] = true;
			for (int i = 0; i < _n; i++)
			{
				if (_matrix[srci][i] != MAX_W && vis[i] == false)
				{
					pq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}

			int n = 0;
			while (!pq.empty())
			{
				Edge eg = pq.top();
				pq.pop();
				// 这里还需要判断，存在这种情况：入堆的时候可能还未选到，但在堆内后，某个顶点被选，之后再选可能会构成环
				// 该顶点未被选过才能进堆
				if (vis[eg._desti] == false)
				{
					w += eg._w;
					vis[eg._desti] = true;
					cout << _vertexs[eg._srci] << "->" << _vertexs[eg._desti] << " " << eg._w << endl;
					minTree._AddEdge(eg._srci, eg._desti, _matrix[eg._srci][eg._desti]);
					n++;
					// 与该顶点相连的最小边，且不与之前选的顶点连通
					for (int i = 0; i < _n; i++)
					{
						if (_matrix[eg._desti][i] != MAX_W && vis[i] == false)
						{
							pq.push(Edge(eg._desti, i, _matrix[eg._desti][i]));
						}
					}
					if (n == _n - 1)
						return w;
				}

			}
			return W();
		}

		void PrintShortPath(const V &src, vector<int> &dist, vector<int> &path)
		{
			int srci = GetVertexIndex(src);
			for (int i = 0; i < _n; i++)
			{
				if (i == srci)
					continue;
				int p = i;
				vector<int> pt;
				while (p != srci)
				{
					pt.push_back(p);
					p = path[p];
				}
				pt.push_back(srci);
				reverse(pt.begin(), pt.end());
				for (int j = 0; j < pt.size(); j++)
				{
					cout << _vertexs[pt[j]] << "->";
				}
				cout << dist[i] << endl;
			}
		}

		// 最短路径无负权 - Dijkstra
		void Dijkstra(const V &src, vector<W> &dist, vector<int> &path)
		{
			// 1.初始化
			path.resize(_n, -1);
			dist.resize(_n, MAX_W);
			int srci = GetVertexIndex(src);
			dist[srci] = 0;
			path[srci] = srci;
			vector<int> set(_n, false); // 最短路径集合

			// 2.遍历每个节点，并更新最短路径
			for (int i = 0; i < _n; i++)
			{
				// a.从未访问节点集合中，获取到起始节点路径最短的节点 u
				//   目的：再以u为起点，去非最短路集合内 寻找下一个最短路径的节点
				int u = 0;
				W min = MAX_W;
				for (int j = 0; j < _n; j++)
				{
					if (dist[j] < min && set[j] == false)
					{
						u = j;
						min = dist[j];
					}
				}
				// b.加入到 最短路径集合内
				set[u] = true;
				// c.松弛更新 u->v的最短路径
				//  s->u->v，s->v 这两种路径中的最小路径
				//  s->u->v：经过多次路径跳转到达v，可得最短路径
				//  s->v：s与v直接相连的边，即为最短路径
				for (int v = 0; v < _n; v++)
				{
					// s：起点,u：中间过程中的节点，v：目标节点
					// s->u->v
					// s->v
					// u要到v，首先s,v得是邻接顶点，当u为s的时候，会更新 s,v相连的情况
					if (_matrix[u][v] != MAX_W && (dist[u] + _matrix[u][v] < dist[v]) && set[v] == false)
					{
						dist[v] = dist[u] + _matrix[u][v];
						path[v] = u;
					}
				}
			}
		}

		bool BellmanFord(const V &src, vector<W> &dist, vector<int> &path)
		{
			int srci = GetVertexIndex(src);
			dist.resize(_n, MAX_W);
			path.resize(_n, -1);
			path[srci] = srci;
			dist[srci] = 0;
			for (int i = 0; i < _n; i++)
			{
				// 一次循环中只要有一次没更新，那么可以直接结束更新
				bool flag = true;
				for (int u = 0; u < _n; u++)
				{
					for (int v = 0; v < _n; v++)
					{
						// 更新 u->v最短路径
						// 每两个节点都要判断一下
						if (_matrix[u][v] != MAX_W && dist[v] > dist[u] + _matrix[u][v])
						{
							dist[v] = _matrix[u][v] + dist[u];
							path[v] = u;
							flag = false;
						}
					}
				}
				if (flag)
					break;
			}
			// 判断是否成环
			for (int u = 0; u < _n; u++)
			{
				for (int v = 0; v < _n; v++)
				{
					// 更新 u->v最短路径
					// 每两个节点都要判断一下
					if (_matrix[u][v] != MAX_W && dist[v] > dist[u] + _matrix[u][v])
					{
						return false;
					}
				}
			}

			return true;
		}

		bool FloydWarShall(vector<vector<W>> &dist, vector<vector<int>> &path)
		{
			// dist[i][j]：表示从i到j的最短路径      dist[i]：i作为srci，此时的最短路径
			// path[i][j]：表示从i到j最短路径的双亲  path[i]：i作为srci，此时的双亲情况
			dist.resize(_n,vector<int>(_n,MAX_W));
			path.resize(_n,vector<int>(_n,-1));
			for(int i = 0; i < _n; i++)
			{
				for(int j = 0; j < _n; j++)
				{
					if(i == j)
					{
						dist[i][j] = W();
						continue;
					}
					if(_matrix[i][j] != MAX_W)
					{
						dist[i][j] = _matrix[i][j];
						path[i][j] = i;
					}
						
				}
			}

			for(int k = 0; k < _n; k++)
			{
				for(int i = 0; i < _n; i++)
				{
					for(int j = 0; j < _n; j++)
					{
						// i -> k -> j
						// i -> j
						// dist[i][j] = min(dist[i][k] + dist[k][j],dist[i][j]);
						// if(_matrix[i][k] != MAX_W && _matrix[k][j] != MAX_W && dist[i][k] + dist[k][j] < dist[i][j])
						// 是dist[i][k]存在路径，而不是_matrix[i][j]存在路径，后面使用的是 dist[i][k] + dist[k][j]
						if(dist[i][k] != MAX_W && dist[k][j] != MAX_W && dist[i][k] + dist[k][j] < dist[i][j])
						{
							dist[i][j] = dist[i][k] + dist[k][j];
							// 找跟j相连的上一个邻接顶点
							// 如果k->j 直接相连，上一个点就k，path[k][j]存就是k
							// 如果k->j 没有直接相连，k->...->x->j，path[k][j]存就是x
							path[i][j] = path[k][j];
						}
					}
				}
					
				// 打印权值和路径矩阵观察数据
				for (int i = 0; i < _n; ++i)
				{
					for (int j = 0; j < _n; ++j)
					{
						if (dist[i][j] == MAX_W)
						{
							printf("%3c", '*');
						}
						else
						{

							printf("%3d", dist[i][j]);
						}
					}
					cout << endl;
				}
				cout << endl;
				for (int i = 0; i < _n; ++i)
				{
					for (int j = 0; j < _n; ++j)
					{
						printf("%3d", path[i][j]);
					}
					cout << endl;
				}
				cout << "=================================" << endl;
			}

		}

	private:
		// 记录顶点与下标的映射关系
		// vertex-index
		unordered_map<V, int> _index;
		// 顶点集合
		// index-vertex
		vector<V> _vertexs;
		// 邻接矩阵，存储顶点之间的关系
		vector<vector<W>> _matrix;
		int _n;
	};

	void TestGraph1()
	{
		Graph<char, int, INT_MAX, true> g("0123", 4);
		g.AddEdge('0', '1', 1);
		g.AddEdge('0', '3', 4);
		g.AddEdge('1', '3', 2);
		g.AddEdge('1', '2', 9);
		g.AddEdge('2', '3', 8);
		g.AddEdge('2', '1', 5);
		g.AddEdge('2', '0', 3);
		g.AddEdge('3', '2', 6);

		g.Print();
	}

	void TestBDFS()
	{
		char a[] = "ABCDEFGHI";
		Graph<char, int, 0, false> g1(a, strlen(a));
		g1.AddEdge('A', 'B', 1);
		g1.AddEdge('A', 'C', 1);
		g1.AddEdge('A', 'D', 1);
		g1.AddEdge('B', 'E', 1);
		g1.AddEdge('B', 'C', 1);
		g1.AddEdge('C', 'F', 1);
		g1.AddEdge('D', 'F', 1);
		g1.AddEdge('E', 'G', 1);

		// g1.AddEdge('F', 'H',1);
		g1.AddEdge('H', 'I', 1);

		g1.Print();

		g1.BFS('A');
		cout << "-----------" << endl;
		g1.DFS('A');
	}

	// 获取最小生成树
	void TestMinTree()
	{
		const char str[] = "abcdefghi";
		Graph<char, int> g(str, strlen(str));
		g.AddEdge('a', 'b', 4);
		g.AddEdge('a', 'h', 8);
		// g.AddEdge('a', 'h', 9);
		g.AddEdge('b', 'c', 8);
		g.AddEdge('b', 'h', 11);
		g.AddEdge('c', 'i', 2);
		g.AddEdge('c', 'f', 4);
		g.AddEdge('c', 'd', 7);
		g.AddEdge('d', 'f', 14);
		g.AddEdge('d', 'e', 9);
		g.AddEdge('e', 'f', 10);
		g.AddEdge('f', 'g', 2);
		g.AddEdge('g', 'h', 1);
		g.AddEdge('g', 'i', 6);
		g.AddEdge('h', 'i', 7);
		Graph<char, int> kminTree;
		cout << "Kruskal:" << endl;
		cout << g.Kruskal(kminTree) << endl;

		Graph<char, int> pminTree;
		cout << "Prim:" << endl;
		cout << g.Prim(pminTree, 'a') << endl;
		pminTree.Print();
		cout << endl;

		// for (size_t i = 0; i < strlen(str); ++i)
		// {
		// 	cout << "Prim: str[i]" << endl << g.Prim(pminTree, str[i]) << endl;
		// }
	}

	void TestGraphDijkstra()
	{
		const char *str = "syztx";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('s', 't', 10);
		g.AddEdge('s', 'y', 5);
		g.AddEdge('y', 't', 3);
		g.AddEdge('y', 'x', 9);
		g.AddEdge('y', 'z', 2);
		g.AddEdge('z', 's', 7);
		g.AddEdge('z', 'x', 6);
		g.AddEdge('t', 'y', 2);
		g.AddEdge('t', 'x', 1);
		g.AddEdge('x', 'z', 4);

		vector<int> dist;
		vector<int> parentPath;
		g.Dijkstra('s', dist, parentPath);
		g.PrintShortPath('s', dist, parentPath);
	}

	void TestGraphBellmanFord()
	{
		const char* str = "syztx";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('s', 't', 6);
		g.AddEdge('s', 'y', 7);
		g.AddEdge('y', 'z', 9);
		g.AddEdge('y', 'x', -3);
		g.AddEdge('z', 's', 2);
		g.AddEdge('z', 'x', 7);
		g.AddEdge('t', 'x', 5);
		g.AddEdge('t', 'y', 8);
		g.AddEdge('t', 'z', -4);
		g.AddEdge('x', 't', -2);
		vector<int> dist;
		vector<int> parentPath;
		if (g.BellmanFord('s', dist, parentPath))
			g.PrintShortPath('s', dist, parentPath);
		else
			cout << "成环" << endl;
	}

	void TestFloydWarShall()
	{
		const char* str = "12345";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('1', '2', 3);
		g.AddEdge('1', '3', 8);
		g.AddEdge('1', '5', -4);
		g.AddEdge('2', '4', 1);
		g.AddEdge('2', '5', 7);
		g.AddEdge('3', '2', 4);
		g.AddEdge('4', '1', 2);
		g.AddEdge('4', '3', -5);
		g.AddEdge('5', '4', 6);
		vector<vector<int>> vvDist;
		vector<vector<int>> vvParentPath;
		g.FloydWarShall(vvDist, vvParentPath);

		// 打印任意两点之间的最短路径
		for (size_t i = 0; i < strlen(str); ++i)
		{
			g.PrintShortPath(str[i], vvDist[i], vvParentPath[i]);
			cout << endl;
		}
	}

}

// 邻接表存储
namespace link_table
{
	template <class W>
	struct Edge
	{
		size_t _srci;  // 起点
		size_t _desti; // 终点
		W _w;		   // 权值
		// Edge* _next; 注意模板!!!

		Edge<W> *_next;

		Edge(size_t srci = -1, size_t desti = -1, const W &w = W())
			: _srci(srci),
			  _desti(desti),
			  _w(w),
			  _next(nullptr)
		{
		}
	};

	// V：顶点的类型
	// W：权值的类型
	// Direction：表示有向图还是无向图
	template <class V, class W, bool Direction = false>
	class Graph
	{
		// using Edge = Edge<W>;
		// typedef Edge<W> Edge; // 这样重命名是不可以的，Linux下不允许，VS中可以
		// Edge 和 外部 struct Edge 编译器不能区分哪个是哪个
		// 另外要注意 模板中的类型是 类型 + 模板参数 才是完整类型，只有类型 并不是真的类型
		typedef Edge<W> Node;

	public:
		// using Edge = Edge<W>;
		// 强制生成默认的构造函数
		Graph() = default;

		// vertexs：顶点信息的起始地址
		// n：顶点的个数
		Graph(const V *vertex, int n)
			: _vertexs(n),
			  _out_table(n, nullptr),
			  _in_table(n, nullptr),
			  _n(n)
		{
			for (int i = 0; i < n; i++)
			{
				_vertexs[i] = vertex[i];
				_index[vertex[i]] = i;
			}
		}
		size_t GetVertexIndex(const V &vertex)
		{
			if (_index.count(vertex) == 0)
			{
				cout << "无效顶点: " << vertex << endl;
				throw invalid_argument("无效顶点");
			}
			return _index[vertex];
		}

		void _AddEdge(size_t srci, size_t desti, const W &w)
		{
			// 进行头插
			Node *edge = new Node(srci, desti, w);
			// src->dest
			edge->_next = _out_table[srci];
			_out_table[srci] = edge;
			cout << "Direction = " << Direction << endl;

			if (Direction == false)
			{
				// desti -> src
				Node *edge = new Node(desti, srci, w);
				edge->_next = _out_table[desti];
				_out_table[desti] = edge;
			}
		}
		// 添加(srcv,destv) srcv -> destv
		// w：权值
		void AddEdge(const V &srcv, const V &destv, const W &w)
		{
			size_t srci = GetVertexIndex(srcv);
			size_t desti = GetVertexIndex(destv);
			_AddEdge(srci, desti, w);
		}

		void Print()
		{
			// 1.打印下标与顶点的映射
			for (int i = 0; i < _n; i++)
			{
				cout << "[" << i << "] -> " << _vertexs[i] << endl;
			}
			cout << endl;

			for (int i = 0; i < _n; i++)
			{
				Node *head = _out_table[i];
				printf("[%d-%s]->", i, _vertexs[i].c_str());
				while (head)
				{
					int in = head->_desti;
					printf("[%d-%s]->", in, _vertexs[in].c_str());
					head = head->_next;
				}
				cout << "nullptr" << endl;
			}
		}

	private:
		// 边与下标的映射
		unordered_map<V, int> _index;
		// 边的集合  i - vertex
		vector<V> _vertexs;
		// 邻接表

		// 出度表
		// 头节点
		vector<Node *> _out_table;
		// 入度表 - 不维护,  一般用的少
		vector<Node *> _in_table;
		int _n;
	};
	void TestGraph1()
	{
		string a[] = {"张三", "李四", "王五", "赵六"};
		Graph<string, int, true> g1(a, 4);
		g1.AddEdge("张三", "李四", 100);
		g1.AddEdge("张三", "王五", 200);
		g1.AddEdge("王五", "赵六", 30);
		g1.Print();
	}
}